//
// Created by Administrator on 2023/8/12.
//
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> intersection(vector<vector<int>> &nums) {
        // 求所有数组的交集 用哈希表
        set<int> s(nums[0].begin(), nums[0].end());
        for (int i = 1; i < nums.size(); i++) {
            // 如果s中存在的数字在nums[i]中不存在，就把这个数字从s中删除
            set<int> tmp(nums[i].begin(), nums[i].end());
            set<int> c;
            // 求tmp和s的交集，结果放在c中
            set_intersection(s.begin(), s.end(), tmp.begin(), tmp.end(), inserter(c, c.begin()));
            s = c;
            if (s.empty())
                break;
        }
        return vector<int>(s.begin(), s.end());

    }
};

class Solution2 {
public:
    vector<int> intersection(vector<vector<int>> &nums) {
        int n = nums.size();
        unordered_set<int> res(nums[0].begin(), nums[0].end());
        for (int i = 1; i < n; ++i) {
            unordered_set<int> tmp;
            // 统计nums[i]中在res里出现的
            for (int num: nums[i]) {
                if (res.count(num)) {
                    tmp.insert(num);
                }
            }
            res = tmp;
        }
        vector<int> ans(res.begin(), res.end());
        sort(ans.begin(), ans.end());
        return ans;
    }
};

class Solution3 {
public:
    vector<int> intersection(vector<vector<int>> &nums) {
        // 统计每个数字出现的次数，等于n的就放到答案里
        int n = nums.size();
        unordered_map<int, int> freq;
        for (const auto &arr: nums) {
            for (int num: arr) {
                ++freq[num];
            }
        }
        vector<int> res;
        for (const auto &[k, v]: freq) {
            if (v == n) {
                res.push_back(k);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};


int main() {
    Solution s;
    vector<vector<int>> nums;
    vector<int> result;
    nums = {{3, 1, 2, 4, 5},
            {1, 2, 3, 4},
            {3, 4, 5, 6}};
    result = s.intersection(nums);
    for (int i: result) {
        cout << i << endl;
    }
    return 0;
}